package datastructure.sort;

import java.util.Arrays;

/**
 * 快速排序
 *
 * @author jack.wu
 * @version 1.0
 * @date 2020-03-25
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] array = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        long startTime = System.currentTimeMillis();
        quickSort(array);
        long endTime = System.currentTimeMillis();
        System.out.println(Arrays.toString(array));
        System.out.println("耗时：" + (endTime - startTime));
    }

    /**
     * 快速排序
     *
     * @param array
     */
    private static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }

    /**
     * 具体实现
     *
     * @param array 待排序数组
     * @param left
     * @param right 结束
     */
    private static void quick(int[] array, int left, int right) {
        if (left > right) {
            return;
        }
        // 定义个基准值
        int pivot = array[left];
        int l = left;
        int r = right;
        int temp = 0;
        while (l < r) {
            // 右边向左找 直到右边小于基准值退出来
            while (l < r && array[r] >= pivot) {
                r--;
            }
            // 左边向右找 直到左边大于基准值退出来
            while (l < r && array[l] <= pivot) {
                l++;
            }
            // 需要交换位置
            if (l < r) {
                temp = array[l];
                array[l] = array[r];
                array[r] = temp;
            }
        }
        // 最后将基准放到中间
        array[left] = array[l];
        array[l] = pivot;
        // 递归调用左半数组
        quick(array, left, l - 1);
        // 递归调用右半数组
        quick(array, l + 1, right);

    }
}
